Thực đơn
Mã hóa Huffman Mã giảTrong đoạn mã giả dưới đây ta dựa trên một mảng các ký hiệu A [ 1.. n ] {\displaystyle A[1..n]} có tần suất tương ứng là W [ 1.. n ] {\displaystyle W[1..n]}
Ta tạo một đống trên cơ sở sắp xếp lại các chỉ số của A và W. Ta lưu trữ đống dưới dạng mảng, ký hiệu nó là Heap[1..n]. Trước hết đưa chỉ số của các chữ cái theo thứ tự ban đầu vào mảng Heap[1..n] với Heap[i]=i. với mọi i=1..n.
Procedure DownHeap(List W,Int k,Int Count){Int i:=k, v:=W(Heap(k)), j While 2*i<=Count { j:=2*i if j+1<= Count and W(Heap(j+1))>W(Heap(j)) then j:=j+1 if W(Heap(j))< v then Heap(i):=Heap(j) else break i:=j Heap(j):=Heap(k) }}
Procedure MakeHeap(List W,Int n){Int k For k:=int(n/2) downto 1 { DownHeap (W,k,n)}}
Ta sẽ lưu trữ cấu trúc của cây mã Huffman vào một mảng. Cây Huffman gồm n lá mỗi lá chứa chỉ số của chữ cái tương ứng. Mỗi lần ghép 2 cây thành một ta phải thêm một đỉnh, như vậy cây biểu diễn mã Huffman gồm 2.n-1 đỉnh. Ta ký hiệu cây này là Huff[1..2n-1]. Vì mỗi gốc mới bổ sung đều có trọng số nên ta mở rộng mảng W[1..n] các trọng số thành mảng W' [1..2n-1]. Gọi m là số đỉnh của cây sẽ xây dựng. lúc đầu ta có n lá, đỉnh bổ sung lần đầu sẽ là n+1, lần thứ 2 là n+2,... Khi lấy ra hai ký tự có tần số nhỏ nhất chẳng hạn ký tự thứ i làm con trái và ký tự thứ j làm con phải của đỉnh mới bổ sung có chỉ số m ta đặt Huff[i]=-m, Huff[j]=m.
Procedure MakeTreeHuffman(List W,Int n){List Heap,Huff Int i,j,count:=n,m:=nMakeHeap(W,n) While Count >1 { i:=Heap(1) Heap(1):= Heap(count) Count:=Count-1 DownHeap(W,1,Count) j:=Heap(1) m:=m+1 Huff(i):=-m Huff(j):=m W(m):=W(i)+W(j) Heap(1):=m DownHeap(W,1,Count) } Return Huff}
Sau khi cấu trúc của cây Huffman được lưu vào mảng Huff ta dễ dàng xây dựng mảng Code[1..n] cho bộ mã nhị phân tiền tố tối ưu của các ký tự A[1..n].
Procedure CodingHuffman(List Huff, n){Int k:=1,j While k<=n { Code(k):="" j:=Huff(k) While Abs(j)<=2*n-1 { If j>0 then Code(k)="1"+Code(k) else Code(k)="0"+Code(k) j:=Huff(abs(j)) } k:=k+1 } Return Code}
Trong các bước trên, giả sử đã xây dựng được bộ mã Huffman của 256 ký hiệu có mã ASCII từ 0 đến 255 chứa trong mảng Code[1..256].Việc nén file có thể phân tích sơ bộ như sau:
Thực đơn
Mã hóa Huffman Mã giảLiên quan
Mã Mã di truyền Mã Siêu Mã số điện thoại quốc tế Mãn Châu Quốc Mã Morse Mã Gia Kỳ Mã vạch Mãn Châu Mã hóa video hiệu quả caoTài liệu tham khảo
WikiPedia: Mã hóa Huffman http://www.cs.sfu.ca/cs/CC/365/li/squeeze http://wiki.cc/php/?title=Huffman http://www.research.att.com/projects/OEIS?Anum=A09... http://alexvn.freeservers.com/s1/huffman_template_... http://www.huffmancoding.com/david/algorithm.html http://www.huffmancoding.com/david/scientific.html http://www.informatik.uni-trier.de/~ley/db/conf/st... http://www.cs.duke.edu/csed/poop/huff/info/ http://web-cat.cs.vt.edu/AlgovizWiki/HuffmanCoding... http://semillon.wpi.edu/~aofa/AofA/msg00040.html